1. Field of the Invention
The present invention relates generally to a round robin arbitration system commonly utilized for resource management within a computer system and, more particularly, to a modification to both the procedure and the circuitry or architecture of a round robin arbitration system to improve both its speed and efficiency.
2. Description of the Related Art
Within a given computer system, such as a Broadband Engine, there exists only a finite number of resources. These resources are commonly referred to as shared resources. Typically, though, there is not a single request for a given shared resource. Instead, there are usually multiple requestors competing for shared resources. These requests must be managed in such a way as to optimize the use of the architecture construct, so as to have the most rapid response and limit the wasting of resources.
A component of the resource management scheme is the round robin arbitration system. Within a round robin system, there exist arrays of sequential logic that arbitrate uses among multiple requestors. The array consists of multiple banks of requestors, for example M banks. Within each bank, there exists a latch for each requester, for example N requestors. There can be very large numbers of both banks and requestors, thus, making the M×N array very large. Hence, it is advantageous to simplify the round robin system and to make it efficient.
In conventional systems, there are two manners in which the round robin arbitration could be accomplished. There is the complex array, which maintains a large hardwired logic array to arbitrate. Also, there is simple pattern array where there is a series of simple logic patterns to arbitrate.
Regarding the complex array, which is more common, a large complex array of logic gates is assembled. The complex logic gate array requires a large spatial area with numerous physical wirings. Hence, one problem is that the numerous physical wirings are difficult to create. Also, one must remember that these arrays or matrices of requestors may be sparse. In other words, not every requestor has a pending request in each bank at a given time. The array of logic gates determines the sparseness and the priority of uses among the competing requestors. However, if there are a very large number of banks, requestors, or both, the equations governing such a logic gate array's arbitration become nearly unmanageable. Hence, for a very complex system, a complex array of logic gates is not feasible.
With the second example, a series of very simple logic gate patterns are utilized. The series of simple logic gate patterns operating on a principle nearly inverse to that of the large logic gate arrays. The simple logic patterns cycle through all of the requestors, essentially utilizing brute force as opposed to a finesse technique of eliminating sparseness utilized by the large logic gate arrays. If there is not an active request, the pointer simply moves onto the next requester in the series. The pointer only advances one requester per cycle and stops when there is an active request. Hence, the amount of circuitry is reduced, but the technique is slow and the latency is increased.
However, within the second example, there are ways for the pointer to “jump” several requestors that are not active. The jumps, though, are limited by the cycles of a synchronous clock. Hence, the amount of gate delay becomes tremendously important. Previously, there was a requirement of a minimum of two NAND gates in order to provide a jump. Therefore, a jump is typically limited to a smaller number of requestors.
Therefore, there is a need for a method and/or apparatus for improving area efficiency and circuit speed for round robin selection logic that addresses at least some of the problems associated with conventional methods and apparatuses for round robin selection logic.